package com.linzm.leetcode.hard.exercises1_20230212;

/**
 * @Author zimingl
 * @Date 2023/2/12 23:29
 * @Description: 环形闯关游戏
 * 力扣挑战赛」中有一个由 N 个关卡组成的环形闯关游戏，关卡编号为 0~N-1，编号 0 的关卡和编号 N-1 的关卡相邻。每个关卡均有积分要求，challenge[i] 表示挑战编号 i 的关卡最少需要拥有的积分。图片.png
 * 小扣想要挑战关卡，闯关的具体规则如下：
 * 初始小扣可以指定其中一个关卡为「开启」状态，其余关卡将处于「未开启」状态。
 * 小扣可以挑战处于「开启」状态且满足最少积分要求的关卡，若小扣挑战该关卡前积分为 score，挑战结束后，积分将增长为 score|challenge[i]（即位运算中的 "OR" 运算）
 * 在挑战某个关卡后，该关卡两侧相邻的关卡将会开启（若之前未开启）
 * 请帮助小扣进行计算，初始最少需要多少积分，可以挑战 环形闯关游戏 的所有关卡。
 * <p>
 * 输入：challenge = [5,4,6,2,7]
 * <p>
 * 输出：4
 * <p>
 * 解释： 初始选择编号 3 的关卡开启，积分为 4 挑战编号 3 的关卡，积分变为
 * 4
 * ∣
 * 2
 * =
 * 6
 * 4∣2=6，开启 2、4 处的关卡 挑战编号 2 的关卡，积分变为
 * 6
 * ∣
 * 6
 * =
 * 6
 * 6∣6=6，开启 1 处的关卡 挑战编号 1 的关卡，积分变为
 * 6
 * ∣
 * 4
 * =
 * 6
 * 6∣4=6，开启 0 处的关卡 挑战编号 0 的关卡，积分变为
 * 6
 * ∣
 * 5
 * =
 * 7
 * 6∣5=7 挑战编号 4 的关卡，顺利完成全部的关卡
 * <p>
 * 输入：challenge = [12,7,11,3,9]
 * <p>
 * 输出：8
 * <p>
 * 解释： 初始选择编号 3 的关卡开启，积分为 8 挑战编号 3 的关卡，积分变为
 * 8
 * ∣
 * 3
 * =
 * 11
 * 8∣3=11，开启 2、4 处的关卡 挑战编号 2 的关卡，积分变为
 * 11
 * ∣
 * 11
 * =
 * 11
 * 11∣11=11，开启 1 处的关卡 挑战编号 4 的关卡，积分变为
 * 11
 * ∣
 * 9
 * =
 * 11
 * 11∣9=11，开启 0 处的关卡 挑战编号 1 的关卡，积分变为
 * 11
 * ∣
 * 7
 * =
 * 15
 * 11∣7=15 挑战编号 0 的关卡，顺利完成全部的关卡
 * <p>
 * 输入：challenge = [1,1,1]
 * <p>
 * 输出：1
 * <p>
 * 1 <= challenge.length <= 5*10^4
 * 1 <= challenge[i] <= 10^18
 */
public class Demo1 {
    public static void main(String[] args) {
        float a = 11.1f;
        char alpha = 'A';
        int foo = 65;
        int foo2 = 0;
        boolean trueExp = true;
        System.out.println(trueExp ? alpha : foo2);
        System.out.println(trueExp ? alpha : foo);
        for (float i = 100000000; i < 100000010; i++) {
            System.out.println(i);
        }
    }

    public long ringGame(long[] challenge) {
        //获取最大的值
        long max = challenge[0];
        for (long x : challenge) {
            max = Math.max(max, x);
        }

        int highPos = 0;
        for (int i = 0; i < 64; i++) {
            if (((max >> i) & 1) == 1) {
                highPos = i;
            }
        }

        long ans = max;
        while (--highPos >= 0) {
            if (((ans >> highPos) & 1) == 0) {
                continue;
            }
            if (checkChallenge(challenge, ans & ~(1L << highPos), max)) {
                ans &= ~(1L << highPos);
            }
        }

        return ans;
    }

    private boolean checkChallenge(long[] challenge, long val, long max) {
        boolean[] visited = new boolean[challenge.length];
        int[] jumpFlag = new int[challenge.length];
        long[] jumpValue = new long[challenge.length];
        for (int i = 0; i < challenge.length; i++) {
            if (challenge[i] > val) {
                continue;
            }
            if (visited[i]) {
                continue;
            }

            int ll = i;
            int rr = i;
            int nr = 0;
            int pl = 0;
            long tmp = val | challenge[i];
            visited[i] = true;

            while (true) {
                //判断成功
                if (tmp >= max) {
                    return true;
                }

                if (challenge[nr = (rr + 1) % challenge.length] <= tmp) {
                    //向右
                    rr = nr;
                    if (visited[rr]) {
                        tmp |= jumpValue[rr];
                        rr = jumpFlag[rr];
                    } else {
                        tmp |= challenge[rr];
                        visited[rr] = true;
                    }
                } else if (challenge[pl = (ll - 1 + challenge.length) % challenge.length] <= tmp) {
                    //向左
                    ll = pl;
                    if (visited[ll]) {
                        tmp |= jumpValue[ll];
                        ll = jumpFlag[ll];
                    } else {
                        tmp |= challenge[ll];
                        visited[ll] = true;
                    }
                } else {
                    //失败，记录信息
                    jumpFlag[ll] = rr;
                    jumpValue[ll] = tmp;
                    jumpFlag[rr] = ll;
                    jumpValue[rr] = tmp;
                    break;
                }
            }
        }
        return false;
    }
}
